package algotithm.leetcode.tree.test124;

import algotithm.leetcode.tree.TreeNode;

/**
 * @author 25068
 * @Date 2021/4/30 9:05
 * @Title 124. 二叉树中的最大路径和
 */
public class Solution {


    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(-10);
        TreeNode node1 = new TreeNode(9);
        TreeNode node2 = new TreeNode(20);
        TreeNode node3 = new TreeNode(15);
        TreeNode node4 = new TreeNode(7);
        root.left = node1;
        root.right = node2;
        node1.left = null;
        node1.right = null;
        node2.left = node3;
        node2.right = node4;
        node3.left = null;
        node3.right = null;
        node4.left = null;
        node4.right = null;

        int res = solution.maxPathSum(root);
        System.out.println(res);
    }

    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }
}
